Richard Feynman^[1] proposed the idea of quantum computing for the first time in 1982. He believes that computers built according to the principles of quantum mechanics are more efficient than classical computers in dealing with a certain type of problem. Only at the end of the 20th century, Deutsch^[2] and Shor^[3] discovered the first two famous quantum algorithms and since then the research of quantum computing has been developed more rapidly. Creating an efficient quantum algorithm plays a crucial role in the manufacture of the quantum computer. Unfortunately, finding a new quantum algorithm is a challenging task.

Quantum random walk (QRW) is a fundamental model of dynamical process and has extensive application in science, such as fast hitting tasks^[4] and energy transport simulation.^[5] In the quantum regime, quantum state has the characteristics of quantum superposition and quantum coherence. Therefore, QRW shows different behaviors from its classic version.^[6,7] These characteristics allow QRW to simulate large-scale quantum many-body systems and realize universal quantum computation without time-dependent control.^[8] For instance, some theoretical researchers have been revealed that QRWs propagating in one dimension (1D) have better transmission characteristics than 1D classical random walks.^[9] A dozen years ago, a quantum search algorithm, which is based on the framework of QRW algorithm with remarkable speed up to their corresponding classical algorithm, was reported in Ref. [10]. Some researchers showed that in principle, any quantum algorithm can be recast as a quantum walk algorithm.^[11] QRWs have been successfully implemented in systems as diverse as NMR,^[12,13] bulk,^[14] and fibre^[15] optics, trapped ions,^[16,17] trapped neutral atoms,^[18] superconducting qubits,^[8] and photonics.^[19–22]

Here, we report an experimental realization of the quantum continuous-time random walk (CTRW) algorithm in the nitrogen-vacancy (NV) center in diamond by a two-qubit programmable quantum processor. We found that QRW has completely different probability distributions from classical random walk. While the probability distributions of the classic CTRW exhibit a uniform distribution, the probability distributions of the quantum CTRW show an oscillating trend.

The concept of quantum CTRW was proposed in Ref. [23]. For the CTRW on an undirected circle, four nodes can be grouped in columns indexed by {0,1,2,3} as shown in Fig. 1(a). Each node is connected with the line on the circle. Every step only occurs between two adjacent nodes. The jumping rate from a node to its neighbour is given by γ, which is a fixed, time-independent constant. This means that the movement between adjacent nodes is determined by the probability γ per unit time. The corresponding 4 × 4 generator matrix^[23] is defined by 1

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. Schematic diagram of a four-node random walk and corresponding two different types of probabilities of time evolution. (a) The circle with four nodes. (b) The probabilities of a particle being at the node 0 over time t in the classical and quantum version of CTRW. The blue dashed line corresponds to the classical case, and red line corresponds to the quantum case.

With such a generator matrix H, it is possible to construct a classical CTRW. The evolution of the probability distribution (superscript C indicates the classical case) at node k at time t is given by 2 The quantum CTRW can be analogized to the classical CTRW by treating the generator matrix as the Hamiltonian in quantum evolution.^[23] The four basis |0⟩,|1⟩,|2⟩,|3⟩ correspond to four nodes {0,1,2,3}. The Schrödinger equation for |ψ(t)⟩ can be written as 3 By measuring the state of a particle at the time t, the probability distribution of the particle at a certain node can be obtained. The probability of the particle at node k is (superscript Q indicates the quantum case). The conservation of probability is guaranteed by the normalization. Considering the walking particle starts moving from node 0, then the probabilities of the particle at node k at time t in the quantum and classical CTRW frames have different characteristics as shown in Fig. 1(b). The probability that a particle of a classical CTRW frame cannot return to the initial position (node 0) after a period of time exhibits gradually decay over time and finally reaches a uniform distribution at the infinite-time limit. While the probability of the particle returning to node 0 under the quantum CTRW frame exhibits periodicity.

To implement quantum CTRW on a circle, an NV center in diamond was used in our experiment. The NV center is a defect in diamond as depicted in Fig. 2(a). The electron spin in NV center can be polarized and read out optically. The coherence time is very long even at the room temperature. The ground state of the electron spin is a spin triplet (S = 1) splitting into three spin sublevels |m_S = 0 ⟩ and |m_S = ± 1⟩. In our experiment, the two-qubit system comprises the electron spin qubit and ¹⁴N nuclear spin qubit. Electron (nuclear) spin states |m_S = 0⟩ and |m_S = −1⟩ (|m_I = +1 ⟩ and |m_I = 0⟩) are encoded as the electron (nuclear) spin qubit without considering the other spin levels as shown in Fig. 2(b).

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. Schematics of NV center in diamond. (a) Atomic structure. (b) Energy levels. The experiments were implemented on the two-qubit system which is composed of four energy levels marked by blue color. The four levels, |mS = 0, mI = +1 ⟩, |mS = 0, mI = 0⟩, |mS = −1, mI = + 1⟩, and |mS = −1, mI = 0 ⟩, are denoted by |0⟩, |1⟩, |2⟩, and |3⟩.

Our diamond sample is a [100] facial bulk diamond and was mounted on a typical optically detected magnetic resonance confocal setup. The substitutional nitrogen concentration of sample is less than 5 ppb and the natural abundance of ¹³C is about 1.1%. By applying a 532-nm green laser and a 500-Gs (1 Gs = 10⁻⁴ T) static magnetic field aligned parallel to the symmetry axis of the NV center, the spin state of the NV center is effectively polarized to (m_S, m_I) = (0,+1).^[24] The static magnetic field is created by a permanent magnet. A coplanar waveguide and a coil were used for feeding the microwave (MW) and radio frequency (RF) pulses, respectively.

Table 1.

Table 1.

Table 1. The parameters of two-qubit programmable processor for quantum CTRW algorithm. . t α β δ θA φA θz,A θB φB θz,B θC φC θz,C θD φD θz,D π/12 0 11π/6 0 π/3 π π 3π/5 0 3π/2 π/3 π π π/2 2π/9 4π/3 π/6 0 0 2π/3 π/2 −π/2 7π/5 3π/4 0 π π/2 −π 8π/5 2π/5 −π/3 π/3 π/4 2π 3π/2 0 0 π 0 3π/2 2π 0 π π/2 0 3π/2 0 0 π/3 0 π/3 0 π −π/9 π/5 π −π/9 3π/4 0 π/6 0 π/2 −π/3 5π/6 5π/12 π π/6 0 4π/15 −π π 0 −8π/9 3π/2 4π/15 0 2π π/2 −7π/6 5π/3 π/2 0 0 π −3π/5 0 −π/4 π π/4 0 7π/10 π/2 4π/3 11π/12 11π/12 3π/5 7π/12 0 0 6π/5 π/2 −π/2 7π/5 3π/2 π 0 π/2 −π/10 7π/12 7π/12 −5π/6 5π/6 2π/3 0 0 π/3 π/2 π/2 π/6 π/3 −π π π/2 2π/3 6π/5 π/2 −2π/3 2π/3 3π/4 0 0 3π/2 −π/2 0 −5π/6 π/2 3π/2 π/2 3π/2 π/2 7π/10 π 13π/10 3π/2 5π/6 0 3π/2 0 2π/5 π 0 5π/6 −π 3π/2 3π/5 π 0 π/2 7π/6 π/3 11π/12 0 0 π/6 π/2 −π/2 9π/7 π/4 0 π π/2 −π/5 7π/10 2π/5 −5π/6 5π/6 π 0 2π 2π −11π/10 −2π/5 −π/3 π π/4 π/2 π/4 0 7π/4 7π/5 π/4 4π/7

Table 1. The parameters of two-qubit programmable processor for quantum CTRW algorithm. .

In our experiment, a two-qubit programmable quantum processor^[25] was used to realize the time evolution of the quantum CTRW. The arbitrary two-qubit unitary operation can be implemented by the programmable quantum processor using the universal quantum circuit with altering the parameters. We chose the universal gate library consisting of single-qubit gates parameterized by the decomposition R_z(φ_z) · R(θ, φ) and an entangling two-qubit gate U_zz = exp(i π S_z ⊗ I_z). Here R(θ, φ) = exp[−i θ(cos φ S_x + sin φ S_y)] corresponds to a rotation of angle θ around the axis in the XY plane. Parameter φ denotes the angle between the axis of rotation and the X axis. R_z(φ_z) represents a rotation of angle φ_z around the Z axis. S_j (j = x, y, z) and I_z are the electron and nuclear spin operators, respectively. According to Eq. (3), the time evolution of the CTRW is obtained by |ψ(t)⟩ = U(t)|ψ(0)⟩, where U(t) = exp(−i Ht). The various U(t) at different time t can be decomposed into U(t) = (C ⊗ D) · V · (A ⊗ B) as shown in Fig. 3(a). The decomposition of the unitary operation U is performed following the two steps in Ref. [25]. The first step is to match the matrix eigenvalues of V in the same local equivalence class as U for confirming the three parameters α, β, and δ shown in the dashed rectangle in Fig. 3(a). The second step is to manipulate the real and orthogonal matrix eigenvectors to obtain the four remaining single qubit operations which are required to map between V and U(t). According to the above two steps, quantum CTRW state evolution can be realized by the universal quantum circuit with fifteen parameters, which are α, β, δ, θ_A, φ_A, φ_z,A, θ_B, φ_B, φ_z,B, θ_C, φ_C, φ_z,C, θ_D, φ_D, and φ_z,D as shown in Table 1.

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. Two-qubit programmable quantum processor in NV center. (a) Circuit diagrams for arbitrary unitary transformations on two qubits. The brackets highlight the decomposition of the two-qubit operation into (C ⊗ D) · V · (A ⊗ B). (b) Realization of the single-qubit gates.

In the experiment, the single qubit rotations on the electron spin are implemented by a hard microwave pulse as shown in Fig. 3(b). The time τ corresponds to the interaction between electron spin and nuclear spin, and t_p is pulse duration time which is controlled by the angle of rotation θ. The single qubit rotations on the nuclear spin are implemented by the decoherence-protected gates which are comprised of dynamical decoupling on the electron spin and nuclear spin driving.

The probabilities as a function of time t are shown in Fig. 4(a), where the blue dashed curve and the gray curve are the simulated results of the classical and quantum cases and the solid circles with error bars are the experimental results. The simulated result is achieved by considering the effect of decoherence, which is aroused by the static fluctuation of the magnetic field. Our results show that the probability of classical CTRW monotonically decreases with time and exhibits a trend of uniform distribution in the end. While the probability of quantum CTRW has a periodic behavior. The experimental results are in good agreement with the simulated ideal cases.

Fig. 4.

Figure Option ViewDownloadNew Window

Fig. 4. Characterization of the performance of CTRWs on a circle. (a) The probabilities of the particle at node 0 at time t. (b) The total variation distances against time. The blue dashed line is the simulation results of classical CTRW. The grey lines represent simulation results of quantum CTRW considering the decoherence effect and imperfect polarization. Black dots with error bars are experimental results of the quantum CTRW. All the error bars on the data points are the standard deviations from the mean.

A straightforward method to characterize the uniformity of a distribution is to use the total variation distance between the given distribution and the uniform distribution. The classical and quantum total variation distance as a function of time t is 4

Figure 4(b) exhibits the the dependence of Δ^C(t) and Δ^Q(t) on time. The classical version of this CTRW approaches the uniform distribution exponentially as time lapses. In contrast, the quantum CTRW shows an oscillating behavior. An interesting property of this quantum CTRW is that Δ^Q(nπ/4γ) = 0 when n is odd, which means that the probability distribution is exactly uniform at times t = π/4γ and its odd multiples. While the classical CTRW only can reach the uniform distribution at the infinite-time limit. It can be seen that the experimental results are consistent with the theoretical predictions. Errors mainly come from decoherence effect and imperfect polarization. When the magnetic field strength is set to 500 {Gs}, the spin state of the NV center is effectively polarized to |m_S = 0⟩ state. After the optical pumping, 95% of the population occupies the |m_S = 0⟩ state of the electron spin and 98% of the population occupies the |m_I = +1⟩ state of the nuclear spin. The imperfect polarization indicates an initialization error of about 7%.

In conclusion, we have realized quantum CTRW algorithm with a solid-state programmable two-qubit quantum processor at room temperature. The programmable quantum processor which is based on the spin qubits in an NV center is used to implement the quantum CTRW algorithm by altering the parameters in the universal quantum circuit. The experimental results demonstrate that the quantum walk yields the oscillating behavior which is reversible and periodic, while the classical counterpart is essentially dissipative. Our work verifies the computational flexibility of the programmable processor, which paves the way to implement various algorithms in a large-scale room-temperature programmable quantum computation architecture.